﻿// ------------------------------------------------------------------------------------------------
//  <copyright file="MultiTree.cs" company="Iveely">
//    Copyright (c) Iveely Liu.  All rights reserved.
//  </copyright>
//  
//  <Create Time>
//    03/02/2013 21:59 
//  </Create Time>
//  
//  <contact owner>
//    liufanping@iveely.com 
//  </contact owner>
//  -----------------------------------------------------------------------------------------------

#region

using System;
using System.Collections.Generic;

#endregion

namespace IveelySE.NLP.Common.DataStructure.Tree
{
    /// <summary>
    ///   多叉树
    /// </summary>
    [Serializable]
    public class MultiTree<T>
    {
        #region 内部类

        /// <summary>
        ///   多叉树结点
        /// </summary>
        /// <typeparam name="T"> 结点类型 </typeparam>
        public class Node
        {
            #region 属性 OR 字段

            /// <summary>
            ///   结点值
            /// </summary>
            public T Value = default(T);

            /// <summary>
            ///   结点编号
            /// </summary>
            public int Id { get; set; }

            /// <summary>
            ///   深度
            /// </summary>
            public int Deep { get; set; }

            /// <summary>
            ///   结点路径
            /// </summary>
            public string Path { get; set; }

            /// <summary>
            ///   父结点
            /// </summary>
            private Node Parent { get; set; }

            /// <summary>
            ///   子结点集合
            /// </summary>
            public IList<Node> Children { get; set; }

            #endregion

            #region 构造方法

            public Node(int id)
            {
                this.Path = id.ToString() + ".";
                this.Id = id;
                this.Deep = 0;
                this.Parent = null;
                this.Children = new List<Node>();
            }

            public Node(int id, T value)
            {
                this.Path = id.ToString() + ".";
                this.Id = id;
                this.Deep = 0;
                this.Parent = null;
                this.Value = value;
                this.Children = new List<Node>();
            }

            public Node(int id, T value, Node parent)
            {
                this.Path = parent.Path + id.ToString() + ".";
                this.Id = id;
                this.Deep = parent.Deep + 1;
                this.Parent = parent;
                this.Value = value;
                this.Children = new List<Node>();
            }

            #endregion

            #region 公有方法

            /// <summary>
            ///   添加子结点
            /// </summary>
            /// <param name="id"> 子结点编号 </param>
            /// <param name="child"> 子结点的值 </param>
            public void AddChild(int id, T child)
            {
                var Child = new Node(id, child, this);
                this.Children.Add(Child);
            }

            public override string ToString()
            {
                return this.Value.ToString();
            }

            #endregion
        }

        #endregion

        #region 属性 OR 字段

        /// <summary>
        ///   根结点
        /// </summary>
        public Node Root { get; set; }

        #endregion

        #region 构造方法

        public MultiTree()
        {
            this.Root = new Node(-1);
        }

        #endregion

        #region 公有方法

        /// <summary>
        ///   根据结点编号查找结点
        /// </summary>
        /// <param name="id"> 被查找结点的编号 </param>
        /// <returns> 返回对应结点 </returns>
        public Node GetNodeById(int id)
        {
            return FindNode(Root, id);
        }

        /// <summary>
        ///   根据值查找结点
        /// </summary>
        /// <param name="value"> 结点值 </param>
        /// <returns> 返回对应结点(第一个) </returns>
        public Node GetNodeByValue(T value)
        {
            return FindNode(Root, value);
        }

        /// <summary>
        ///   通过值获取某个结点的到达路径
        /// </summary>
        /// <param name="value"> 结点值 </param>
        /// <returns> 路径 </returns>
        public string GetNodePathByValue(T value)
        {
            Node node = FindNode(this.Root, value);
            if(node != null)
            {
                return node.Path;
            }
            return "";
        }

        /// <summary>
        ///   添加结点
        /// </summary>
        /// <param name="id"> 被添加结点编号 </param>
        /// <param name="value"> 被添加结点的值 </param>
        /// <param name="parentId"> 被添加结点的父亲结点编号 </param>
        public void AddNode(int id, T value, int parentId)
        {
            if(id == parentId)
            {
                Root.AddChild(id, value);
            }
            Node parent = GetNodeById(parentId);
            if(parent != null)
            {
                parent.AddChild(id, value);
            }
            else
            {
                throw new NullReferenceException(
                    "[IveelySE.NLP.Common.DataStructure.Tree.MultiTree.AddNode(int id,T value,int parentId)]:无法找到对应的parentId.");
            }
        }

        #endregion

        #region 私有方法

        /// <summary>
        ///   根据Id查找结点
        /// </summary>
        /// <param name="node"> 入口结点，从此结点开始查找 </param>
        /// <param name="id"> 被查找结点的Id </param>
        /// <returns> 返回该编号的结点 </returns>
        private Node FindNode(Node node, int id)
        {
            Node result = null;
            if(node != null && node.Id == id)
            {
                return node;
            }
            foreach(Node child in node.Children)
            {
                if(child.Id == id)
                {
                    return child;
                }
                if(child.Children != null && child.Children.Count > 0)
                {
                    result = FindNode(child, id);
                    if(result != null)
                    {
                        break;
                    }
                }
            }
            return result;
        }

        /// <summary>
        ///   根据结点值查找结点
        /// </summary>
        /// <param name="node"> 入口结点，从此结点开始查找 </param>
        /// <param name="id"> 被查找结点的值 </param>
        /// <returns> 返回该值的结点 </returns>
        private Node FindNode(Node node, T value)
        {
            Node result = null;
            if(node.Value != null && node.Value.Equals(value))
            {
                return node;
            }
            foreach(Node child in node.Children)
            {
                if(child.Value.Equals(value))
                {
                    return child;
                }
                if(child.Children != null && child.Children.Count > 0)
                {
                    result = FindNode(child, value);
                    if(result != null)
                    {
                        break;
                    }
                }
            }
            return result;
        }

        #endregion

        #region 测试

        public static void Test()
        {
            var tree = new MultiTree<string>();
            tree.AddNode(1, "11", -1);
            tree.AddNode(2, "22", -1);
            tree.AddNode(3, "22", -1);
            tree.AddNode(11, "1111", 1);
            tree.AddNode(22, "2222", 2);
            tree.AddNode(33, "3333", 3);
        }

        #endregion
    }
}